#include "../8.3.2.Adjacency list/ljb.h"

int visited[M]; // 访问标志数组

/**
 * 从顶点i出发，广度优先遍历图
 * @param {LinkedGraph}     g               图的邻接表存储结构
 * @param {int}             i               顶点下标
 * @return void
 */
void bfs(LinkedGraph g, int i)
{
    int j;
    EdgeNode *p;
    int queue[M], front = 0, rear = 0;
    // 访问顶点vi
    printf("%c \n", g.adjlist[i].vertex);
    visited[i] = 1;
    queue[rear++] = i;

    while (rear > front)
    {
        j = queue[front++];
        p = g.adjlist[j].Firstedge;
        while (p)
        {
            if (!visited[p->adjvex])
            {
                printf("%c \n", g.adjlist[p->adjvex].vertex);
                queue[rear++] = p->adjvex;
                visited[p->adjvex] = 1;
            }
            p = p->next;
        }
    }
}

/**
 * 广度优先遍历图
 * @param {LinkedGraph}     g               图的邻接表存储结构
 * @return int
 */
int BfsTraverse(LinkedGraph g)
{
    int i, count = 0;
    for (i = 0; i < g.n; i++)
    {
        visited[i] = 0;
    }
    for (i = 0; i < g.n; i++)
    {
        if (!visited[i])
        {
            printf("\n");
            count++;
            bfs(g, i);
        }
    }
    return count;
}
